#ifndef QUAD_TREE_H
#define QUAD_TREE_H

#include <list>
#include <deque>
#include "Line.h"
#include "IntersectionDetection.h"
#include "CollisionWorld.h"
#include <cilk/reducer_list.h>

//Quadtree Node, the internal elements used in creating the quadtree.
struct QtNode {
   QtNode *parent;   //NULL at head or points to parent
   QtNode *children; //NULL for if there are no children, otherwise points to list of 4
   list<Line*> lines;//Lines contained at this level in the quadtree
  
  //Boundaries
   double min_x;
   double max_x;
   double min_y;
   double max_y;
  
   int depth; //Depth of current node; top level is 1, 2nd is 2, etc.
};

//Structure for canning information about intersections
struct IntersectionInfo {
   Line *l1;
   Line *l2;
   IntersectionType intersectionType;
   
   IntersectionInfo(Line *l1, Line *l2, IntersectionType intersectionType) {
      this->l1 = l1;
	  this->l2 = l2;
	  this->intersectionType = intersectionType;
   }
};

//Nodes in the DAG used for keeping track of what lines exist in our ancestor Quadtree nodes while
//allowing for multi-threaded recursion.
struct DagNode {
   DagNode *next;
   Line *line;
   
   DagNode(DagNode *next, Line *line) {
      this->next = next;
	  this->line = line;
   }
};

//Quadtree for managing various operations
class QuadTree {
protected:
   QtNode *head;
   cilk::reducer_list_append<IntersectionInfo> intersections;
public:
   QuadTree(vector<Line*>*, double, double, double, double);
   ~QuadTree();
   void checkCollisions(CollisionWorld *world);
private:
   void __recurseNodes(QtNode*);
   void __deleteRecurse(QtNode*);
   void __checkCollisionsRecurse(QtNode *, DagNode *, CollisionWorld *);
};


#endif  /* QUAD_TREE_H */